In order to communicate with a user, a computer must be able to output information to a display. In a graphics system, the display is defined by an array of pixels. For example, in a standard-mode VGA (Video Graphics Adapter) system, the screen is addressed as an array of 640.times.480 pixels. Each pixel on the display may be set to a desired color from a defined palette. Typically 16 or 256 color palettes are supported. The number of pixels which may be displayed is defined by the graphic subsystem. Typical VGA modes support 640.times.480, 800.times.600, and 1024.times.768 resolutions. VGA modes with resolution greater than 640.times.480 are generally referred to as "super VGA".
Many of today's application programs are graphics intensive. For example, a computer-aided design program, such as AUTOCAD by AutoDesk, Inc., Sauseleto, Calif., may spend a substantial amount of time drawing a figure to the screen. In some cases, even a small change in the drawing will require the entire drawing to be redrawn. Consequently, the ability of the graphics processor to draw lines quickly becomes of critical importance.
The problems associated with line drawing have been well documented for a number of years. Many of these problems are addressed in an article "Ambiguity in Incremental Line Rastering", by Jack E. Bresenham, IEEE Computer Graphics & Applications May, 1987, which is incorporated by reference herein. The Bresenham article describes problems in drawing a line using an array of pixels, since lines having real values between two discrete pixels will have to approximated using one pixel or the other. Because of the inaccuracies inherent in approximating the line, issues concerning the retraceability of lines and the handling of symmetric figures made up of polylines become important. Consequently, the flexibility of a graphics processor, i.e., the ability of the graphics processor to facilitate modification of the line drawing parameters is highly desirable.
In many instances, for example, where a computer uses windowing software, such as MICROSOFT WINDOWS (from Microsoft Corporation of Redmond, Wash.), an image 10 will be cropped to fit within a rectangular port or "window" 12 of a display 14, as shown in FIG. 1. As the image is cropped, the screen is updated, requiring each line of the image to be redrawn. For example, in FIG. 1, each line 13 which of the image which intersects an edge of the window 12 must be redrawn such that only the points within the window 12 (i.e., the scissored points) are displayed. To redraw the lines, the end points of the scissored line must be recalculated and the lines regenerated. While this example assumes that the image is to be cropped to the portion inside the window, it may be desirable to crop the image to that portion outside the window 12.
A number of methods for redrawing the lines within a window have been developed. The most popular method, the Cohen-Sutherland method, uses both multiplication and division to determine which lines are clipped. If a large number of lines are present in the image, which is very likely in a CAD environment, this method can be very time consuming. Further, the divisions required by the Cohen-Sutherland method (and other similar methods) make the method difficult to implement in hardware.
Therefore, a need has arisen in the industry for a high-speed circuit for drawing lines within a boundary of a rectangle which can be implemented in hardware or software.